#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/2/23 11:36
@Author  : Chen Liu
@FileName: class.py
@Software: PyCharm
"""


# 解法一：每次删除入度为1的点及其对应的边，如果删除后还有剩余节点，说明存在环，否则不存在环。
# 运行超时
# class Solution:
#     def count(self, node, pre):
#         dic = {}
#         # 统计每个点的入度
#         for i in node:
#             dic[i] = 0
#             for j in pre:
#                 if i == j[0] and j[1] != -1:
#                     dic[i] = dic.get(i, 0) + 1
#         return dic
#
#     def canFinish(self, numCourses, prerequisites):
#         if prerequisites is None or len(prerequisites) <= 1:
#             return True
#
#         node = [i for i in range(numCourses)]
#
#         while node:
#             flag = True
#             dic = self.count(node, prerequisites)
#             print("dic: ", dic)
#             for key in node:
#                 if dic[key] == 0:
#                     flag = False
#                     node.remove(key)
#                     for j in prerequisites:
#                         # print(j)
#                         if j[1] == key:
#                             print(j)
#                             j[1] = -1
#
#                 print("pre: ", prerequisites)
#
#             if flag:
#                 break
#
#         print("node: ", node)
#         if node:
#             return False
#         else:
#             return True


# 解法二与解法一思路相同，没有超时的原因是字典统计的是每个点对应的节点。
# 循环终止的条件是课程集合没有发生变化，即列表的长度没有发生改变
# class Solution:
#     def canFinish(self, numCourses, prerequisites):
#         dic = {}
#         for a, b in prerequisites:
#             dic[a] = dic[a] + [b] if a in dic else [b]
#
#         node = list(range(numCourses))
#         t = len(node) + 1
#         while len(node) < t:
#             # 利用长度判断是否发生改变
#             t = len(node)
#             for n in node:
#                 if n not in dic:
#                     node.remove(n)
#                     for x in list(d.keys()):
#                         if n in d[x]:
#                             d[x].remove(n)
#                             # 如果该点的边都删除完了，则该点的入度为0，从字典中删除该点
#                             if d[x] == []:
#                                 dic.pop(x)
#
#         return node == []


# 解法三：深度优先遍历--递归
class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        for k, v in prerequisites:
            graph[k].append(v)

        visit = [0] * numCourses
        # 判断是否找到环--递归
        def dfs(i):
            if visit[i] == 1:
                return True
            if visit[i] == -1:
                return False

            visit[i] = -1
            for pre in graph[i]:
                if not dfs(pre):
                    return False

            visit[i] = 1
            return True

        for i in range(numCourses):
            if not dfs(i):
                return False

        return True


if __name__ == "__main__":
    s = Solution()
    p = [[1, 0], [1, 2], [0, 1]]
    res = s.canFinish(3, p)
    print(res)

